|
对于图论这个专题，以问题为导向，进行学习，主要探究了如下问题： 1）可达矩阵的计算 2）邻接矩阵和关联矩阵的转换 3）图的连通性的计算 4）最小生成树的计算 5）Euler图和hamilton图的判断 下面，我们具体分析每一个问题：  matlab实现代码：
function P = dgraf( A )
%A为图的邻接矩阵
%P为图的可达矩阵
n=size(A,1);
P=A;
for i=2:n
P=P+A^i;
end
P(P~=0)=1;
P;
end
4）应用举例： A=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 10]; P=dgraf(A); P=[1 1 1 1;1 1 1 1;1 1 1 1;1 1 1 1];
 matlab实现代码：
function W = incandadf( F,f )
%仅适用于无向图
%W是输出矩阵
%F是输入矩阵
%f=0时，表示邻接矩阵转关联矩阵，f=1表示关联矩阵转邻接矩阵
if f==0
m=sum(sum(F))/2;
n=size(F,1);
W=zeros(n,m);
k=1;
for i=1:n
for j=i:n
if F(i,j)~=0
W(i,k)=1;
W(j,k)=1;
k=k+1;
end
end
end
elseif f==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
for i=1:m
a=find(F(:,i)~=0);
W(a(1),a(2))=1;
W(a(2),a(1))=1;
end
else
fprintf('f error');
end
W;
end
function W = mattransf( F,f )
%仅适用于有向图
%W是输出矩阵
%F是输入矩阵
%f=0时，表示邻接矩阵转关联矩阵，f=1表示关联矩阵转邻接矩阵
if f==0
m=sum(sum(F));
n=size(F,1);
W=zeros(n,m);
k=1;
for i=1:n
for j=1:n
if F(i,j)~=0
W(i,k)=1;
W(j,k)=-1;
k=k+1;
end
end
end
elseif f==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
for i=1:m
a=find(F(:,i)~=0);
if F(a(1),i)==1
W(a(1),a(2))=1;
else
W(a(2),a(1))=1;
end
end
else
fprintf('f error');
end
W;
end
3）应用举例： F=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 10]; W=incandadf(F,0); W=[1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1]; W1=incandadf(W,1); W1=[0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0];
 matlab实现代码：
function [S,Q] = concom( G )
%图的连通性计算
%G表示图的邻接矩阵
%S表示顶点所分的块数
%Q表示每个顶点所在的块号
n=size(G,1);
m=sum(sum(G))/2;
S=0;
j=1;
C=1;
Q=zeros(n,1);
for i=1:n
for j=(i+1):n
if G(i,j)==1
if Q(i)==Q(j)
if Q(i)==0
Q(i)=C;
Q(j)=C;
C=C+1;
S=S+1;
end
else
if Q(i)==0
Q(i)=Q(j);
elseif Q(j)==0
Q(j)=Q(i);
else
for k=1:n
if Q(k)==Q(i)
Q(k)=Q(j);
end
end
S=S-1;
end
end
end
end
end
S;
Q;
end
3）应用举例： G=[0 1 0 0;1 0 0 0;0 0 0 1;0 0 1 0]; [S,Q]=concom(G) S = 2; Q =[1 1 2 2];  matlab实现代码：
3）Matlab代码：
function [MST,weight] = Kruskal( W )
n=length(W);
T=zeros(n);
W2=W;
for i=1:n
for j=1:n
if W(i,j)==inf
W2(i,j)=0;
end
end
end
m=((nnz(W2))/2);
j=0;
for i=1:m
if j |